#!/usr/bin/env python

import numpy

class Particle(object):

    def __init__(self):
        self.x = 0.0
        self.y = 0.0
        self.fish = None # no fish for you

class BoundingBox(object):
    
    def __init__(self, x_origin, y_origin, side_length):
        # assume origin starts at bottom left corner
        self.x_origin = x_origin
        self.y_origin = y_origin
        self.side_length = side_length

class Quadrant:
    TOP_LEFT = 0
    TOP_RIGHT = 1
    BOT_LEFT = 2
    BOT_RIGHT = 3

class QuadTreeNode(object):
    
    def __init__(self, bounding_box):
        self.bounding_box = bounding_box
        self.parent = None
        self.children = {} # python dict type
        self.particle = None
        self.num_particles = 0

    def isleaf(self):
        return (len(self.children) == 0)

class QuadTree(object):

    def __init__(self, num_particles, bounding_box):
        self.root = QuadTreeNode(bounding_box)
        self.root.num_particles = num_particles

    def get_particle_quadrant(self, particle, bounding_box):
        bot_left_x = bounding_box.x_origin
        bot_left_y = bounding_box.y_origin
        bot_right_x = bounding_box.x_origin + bounding_box.side_length 
        top_left_y = bounding_box.y_origin + bounding_box.side_length 
        mid_x = bot_right_x + float((bot_right_x - bot_left_x)/2)
        mid_y = bot_left_y + float((top_left_y - bot_left_y)/2)
        if (particle.x < mid_x and particle.y < mid_y):
            return Quadrant.BOT_LEFT
        if (particle.x < mid_x and particle.y > mid_y):
            return Quadrant.TOP_LEFT
        if (particle.x > mid_x and particle.y < mid_y):
            return Quadrant.BOT_RIGHT
        if (particle.x > mid_x and particle.y > mid_y):
            return Quadrant.TOP_RIGHT

    def get_particle_bounding_box(self, particle, bounding_box):
        bot_left_x = bounding_box.x_origin
        bot_left_y = bounding_box.y_origin
        bot_right_x = bounding_box.x_origin + bounding_box.side_length 
        top_left_y = bounding_box.y_origin + bounding_box.side_length 
        mid_x = bot_right_x + float((bot_right_x - bot_left_x)/2)
        mid_y = bot_left_y + float((top_left_y - bot_left_y)/2)
        if (particle.x < mid_x and particle.y < mid_y):
            box = BoundingBox(bot_left_x, bot_left_y, bounding_box/2)
            return box
        if (particle.x < mid_x and particle.y > mid_y):
            box = BoundingBox(bot_left_x, mid_y, bounding_box.side_length/2)
            return box
        if (particle.x > mid_x and particle.y < mid_y):
            box = BoundingBox(mid_x, bot_left_y, bounding_box.side_length/2)
            return box
        if (particle.x > mid_x and particle.y > mid_y):
            box = BoundingBox(mid_x, mid_y, bounding_box.side_length/2)
            return box

    def get_child_bounding_box(quadrant, parent_bounding_box)
        bot_left_x = parent_bounding_box.x_origin
        bot_left_y = parent_bounding_box.y_origin
        bot_right_x = parent_bounding_box.x_origin + parent_bounding_box.side_length 
        top_left_y = parent_bounding_box.y_origin + parent_bounding_box.side_length 
        mid_x = bot_right_x + float((bot_right_x - bot_left_x)/2)
        mid_y = bot_left_y + float((top_left_y - bot_left_y)/2)

        if (quadrant == Quadrant.BOT_LEFT):
            box = BoundingBox(bot_left_x, bot_left_y, parent_bounding_box/2)
            return box
        if (quadrant == Quadrant.TOP_LEFT)):
            box = BoundingBox(bot_left_x, mid_y, parent_bounding_box.side_length/2)
            return box
        if (quadrant == Quadrant.BOT_RIGHT)):
            box = BoundingBox(mid_x, bot_left_y, parent_bounding_box.side_length/2)
            return box
        if (quadrant == Quadrant.TOP_RIGHT)):
            box = BoundingBox(mid_x, mid_y, parent_bounding_box.side_length/2)
            return box

    def eliminate_empty(self, root):
        #FIXME: not convinced this is right
        nodeq = deque([])
        nodeq.append(root)
        while (len(nodeq) > 0):
            node = nodeq.popleft()
            for child in node.children:
                if child.num_particles == 0:
                    del child
                else:
                    nodequeue.append(child)

    def quadinsert(self, particle, node):
        #FIXME: might be an issue with when num_particles gets updated - think this through
        particle_box = self.get_particle_bounding_box(particle, node.bounding_box)            
        particle_quadrant = self.get_particle_quadrant(particle, node.bounding_box)

        if (node.num_particles > 1):
            child = QuadTreeNode(particle_box)
            node.children[particle_quadrant] = child
            child.parent = node
            self.quadinsert(particle, child)
        
        elif (node.num_particles == 1): 
            bot_left_box = get_child_bounding_box(Quadrant.BOT_LEFT, node.bounding_box)
            bot_left_child =  QuadTreeNode(bot_left_box)
            node.children[Quadrant.BOT_LEFT] = bot_left_child
            bot_left_child.parent = node

            top_left_box = get_child_bounding_box(Quadrant.TOP_LEFT, node.bounding_box)
            top_left_child =  QuadTreeNode(top_left_box)
            node.children[Quadrant.TOP_LEFT] = top_left_child
            top_left_child.parent = node

            bot_right_box = get_child_bounding_box(Quadrant.BOT_RIGHT, node.bounding_box)
            bot_right_child =  QuadTreeNode(bot_right_box)
            node.children[Quadrant.BOT_RIGHT] = bot_right_child 
            bot_right_child.parent = node

            top_right_box = get_child_bounding_box(Quadrant.TOP_RIGHT, node.bounding_box)
            top_right_child =  QuadTreeNode(top_right_box)
            node.children[Quadrant.TOP_RIGHT] = top_right_child
            top_right_child.parent = node

            if (particle_quadrant == Quadrant.BOT_LEFT):
                quadinsert(particle, bot_left_child)
            if (particle_quadrant == Quadrant.TOP_LEFT)):
                quadinsert(particle, top_left_child)
            if (particle_quadrant == Quadrant.BOT_RIGHT)):
                quadinsert(particle, bot_right_child)
            if (particle_quadrant == Quadrant.TOP_RIGHT)):
                quadinsert(particle, top_right_child)

        elif (node.num_particles == 0):
            node.num_particles += 1
            node.parent.num_particles += 1
            node.particle = particle
        
    def quadtreebuild(self, particles):
        for i in range(len(particles)):
            self.quadinsert(particles[i], self.root)
        self.eliminate_empty()

